#
# @lc app=leetcode.cn id=90 lang=python
#
# [90] 子集 II
#

# @lc code=start
# ## 排序后!=前法
# class Solution(object):
#     def subsetsWithDup(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: List[List[int]]
#         """
#         self.nums = nums
#         self.nums.sort()
#         self.result = []
#         self.sub = []
#         self.loop(0)
#         return self.result

#     def loop(self, index):
#         self.result.append(self.sub[:])
#         if index == len(self.nums):
#             return

#         for i in range(index, len(self.nums)):
#             if i > index:
#                 if self.nums[i]==self.nums[i-1]:
#                     continue
#             self.sub.append(self.nums[i])
#             self.loop(i+1)
#             self.sub.pop()

## set法
class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.nums = nums
        self.nums.sort()
        self.result = []
        self.sub = []
        self.loop(0)
        return self.result

    def loop(self, index):
        self.result.append(self.sub[:])
        if index==len(self.nums):
            return 

        cset = set()
        for i in range(index, len(self.nums)):
            if self.nums[i] in cset:
                continue
            cset.add(self.nums[i])
            self.sub.append(self.nums[i])
            self.loop(i+1)
            self.sub.pop()
        
# @lc code=end

